In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an appropriately chosen learning rate, the social and individual regrets can be bounded by $O(\log(mn))$ in terms of the numbers of actions $m$ and $n$ of the two players. This study investigates the optimality of the dependence on $m$ and $n$ in the regret of optimistic Hedge. To this end, we begin by refining existing regret analysis and show that, in the strongly-uncoupled setting where the opponent's number of actions is known, both the social and individual regret bounds can be improved to $O(\sqrt{\log m \log n})$. In this analysis, we express the regret upper bound as an optimization problem with respect to the learning rates and the coefficients of certain negative terms, enabling refined analysis of the leading constants. We then show that the existing social regret bound as well as these new social and individual regret upper bounds cannot be further improved for optimistic Hedge by providing algorithm-dependent individual regret lower bounds. Importantly, these social regret upper and lower bounds match exactly including the constant factor in the leading term. Finally, building on these results, we improve the last-iterate convergence rate and the dynamic regret of a learning dynamic based on optimistic Hedge, and complement these bounds with algorithm-dependent dynamic regret lower bounds that match the improved bounds.

Neural Information Processing Systems http://nips.cc/

One of its earliest instantiations can be traced to Brown's proposal [

Summary and Contributions: Standard low-regret algorithms guarantee O(sqrt(T)) regret after T rounds (which is tight). One common application of low-regret algorithms is to play an n-action game (in settings like this, it is known that if all players are running low-regret algorithms, then their empirical strategies will converge to specific types of equilibria for the game). It was shown in a series of works that in this more structured setting, it is possible to design algorithms with better regret guarantees; in particular, Syrgkanis et al show that an algorithm known as "Optimistic Hedge" (a generalization of the standard "hedge" / multiplicative weights algorithm) achieves regret bounds on the order of O(T {1/4}) when players in 2 player games both play it. This paper examines the Optimistic Hedge algorithm in further detail, significantly improving the bounds shown by Syrgkanis et al. Specifically, this paper: 1. Shows that if both players in a two-player game run Optimistic Hedge, each player's regret is at most O (T {1/6}). These improvements rely on the fact that Optimistic Hedge converges quickly if the loss vectors and strategies it outputs are relatively stable.